package _08_DFS_BFS;


import java.util.HashSet;
import java.util.Set;

public class _869_重新排序得到2的幂 {


    public static void main(String[] args) {

        _869_重新排序得到2的幂 v = new _869_重新排序得到2的幂();

        System.out.println(v.reorderedPowerOf2(46));

    }

    private Set<String> set = new HashSet<>();

    // 使用hash表记录二的幂
    public boolean reorderedPowerOf2(int n) {
        init();
        return set.contains(countToSet(n));
    }

    // 初始化所有2的幂次方数据
    private void init() {
        for (int i = 1; i <= 1e9; i <<= 1) {
            set.add(countToSet(i));
        }
    }

    private String countToSet(int n) {
        char[] chars = new char[10];
        while (n > 0) {
            ++chars[n % 10];
            n /= 10;
        }
        return new String(chars);
    }

    public boolean reorderedPowerOf23(int n) {
        // 将数字装换为字符
        String str = String.valueOf(n);
        // 排列获取所有字符
        int len = str.length();
        char[] chars = str.toCharArray();
        return dfs(chars, 0, len, 0);
    }

    private boolean dfs(char[] chars, int index, int len, int total) {
        if (index == len) {
            if ((total & (total - 1)) == 0) return true;
        }

        for (int i = index; i < len; i++) {
            if (index != 0 || chars[i] != '0') {
                // 和第一个元素交换
                swap(chars, index, i);
                if (dfs(chars, index + 1, len, total * 10 + (chars[index] - '0'))) return true;
                swap(chars, index, i);
            }
        }

        return false;
    }

    private void swap(char[] chars, int index1, int index2) {
        char temp = chars[index1];
        chars[index1] = chars[index2];
        chars[index2] = temp;
    }

}
